package 子集II;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author: AirMan
 * @date: 2025/4/16 10:20
 * @description: 给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
 * 说明：解集不能包含重复的子集。
 * 示例:
 * 输入: [1,2,2]
 * 输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
 */
public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        // 子集问题就是求树中所有的树节点 ==》 采用回溯法
        // 回溯的参数：nums，startIndex，used，path，result
        // 回溯的返回值：void
        // 回溯的终止条件：startIndex >= nums.length，终止条件在for循环中已囊括了，可以不额外添加
        // 单层回溯的逻辑：
        // 横向遍历过程中，就是避免出现子集重复现象，但是光有for循环不够，还需要引入一个used数组，用来记录相同元素，是否在前一次的for循环中使用过了！
        // 纵向遍历不用担心元素重复问题，因为对于一个分支来说，每加入一个元素就是一个新的子集。1,2,2这种虽然2重复了，但是他也是一个新的子集，所以他的重复问题需要和横向遍历区分开
        // 如何区分？：观察下面两种情况
        // ① used[i-1] && nums[i] == nums[i-1]
        // ② !used[i-1] && nums[i] == nums[i-1]
        // ==》从数层的角度看，因为每次都是回溯结束之后开启一个新的树枝，所以used[i-1]总是false
        // ==》从同一数枝的角度看，因为每次都是将前一元素该为true之后才进行递归搜索的，所以used[i-1]总是trues
        // ③ used数组本意就是为了区分树枝和树层，其实我们可以通过 i > start 进行区分
        // ==》如果是同一树层，因为 for 循环，i会递增，只要递增了 那么一定是 i > startIndex
        // ==》如果是同一树枝，因为 递归的时候，传入新的 startIndex，且 i 被初始化为 startIndex，新树枝一定不满足 i > startIndex

        used = new boolean[nums.length];
        Arrays.fill(used, false);
        Arrays.sort(nums);
        backtracking(nums, 0);
        return result;
    }

    boolean[] used;
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public void backtracking(int[] nums, int startIndex) {

        // 保存所有的树节点
        result.add(new ArrayList<>(path));

        // 终止条件 ==》 for循环已经包含了
//        if (startIndex >= nums.length) {
//            return;
//        }

        // 左闭右开
        for (int i = startIndex; i < nums.length; i++) {
            if (i > 0 && nums[i - 1] == nums[i] && !used[i - 1]) {
                // 需要数层去重
                continue;
            }
//            if (i > 0 && nums[i - 1] == nums[i] && used[i - 1]) {
//                // 树枝不需要去重逻辑，允许子集出现重复元素
//            }
            used[i] = true;
            path.add(nums[i]);
            backtracking(nums, i + 1);
            used[i] = false;
            path.remove(path.size() - 1);
        }

    }
}
